package com.neu.struct.Hash;

/**
 * 散列表（哈希表）
 *   在直接寻址方式下，具有关键字k的元素被存放在槽k中。在散列方式下，该元素存放在槽h(k)中，
 *   即利用散列函数h，由关键字k计算出槽的位置。函数h将关键字的全域U映射到散列表T的槽位上。
 * 冲突：两个关键字可能映射到同一个槽中。
 * 通过链接法解决冲突：
 *   在链接法中，把三列岛同一槽中的所有元素都存放在一个链表中。假设有多个元素被散列到槽j中。
 *   槽j中有一个指针，它指向存储所有散列到j的元素的链表的表头；如果不存在这样的元素，则槽j中为null。
 *   通过链接法解决冲突，每个散列表槽T[j]都包含一个双向链表(删除操作快一些)，其中所有关键字的散列值均为j
 * 插入操作的最坏情况运行时间为O(1)。插入过程在某种程度上要快一些，因为假设待插入的元素x没有出现在表中；
 * 如果需要，可以在出入前执行一个搜索来检查这个假设（需要付出额外代价）
 * 查找操作的最坏情况运行时间与表的长度成正比
 *
 * 链接法散列的性能分析：
 * 给定一个能存放n个元素的、具有m个槽位的散列表T，定义T的装载因子a为n/m，即一个链的平均存储元素数。
 * a可以小于、等于、大于1。
 * 用链接法散列的最坏情况性能很差：所有的n个关键字都散列到同一个槽中，从而产生出长度为n的链表。
 * 这时，最坏情况下查找的时间为O(n)，再加上计算散列函数的时间，如此就和用一个链表来连接所有的元素差不多了。
 * 散列法的平均性能依赖于所选取的散列函数h，将所有的关键字集合分布在m个槽位上的均匀程度。假设给定的元素满足简单均匀散列
 * 定义：简单均匀散列：任何一个给定的元素等可能地散列到m个槽中的任何一个，且与其他元素被散列到什么位置无关，
 * 定理：①在简单均匀散列的情况下，对于用链接法解决冲突的散列表，一次不成功查找的平均时间为O(1+a)。
 *      ②在简单均匀散列大情况下，对于用链接法解决冲突的散列表，一次成功查找的平均时间为O(1+a)。
 *
 *
 *散列函数：
 * 一个好的散列函数应满足简单均匀假设：每个关键字都等可能的被散列到m个槽中的任何一个，并且与其他关键字已散列到哪个槽位无关。
 * 将关键字转换为自然数：
 *      多数散列函数都假定关键字的全域为自然数集。因此，如果所给瓜念子不是自然数，就需要找到一种方法来将他们转换为自然数。
 *      例如，一个字符串就可以被转换为按适当的基数符号表示的整数
 *除法散列法：
 *   在用来设计散列函数的除法散列法中，通过取k除以m的余数，将关键字k映射到m个槽位上的某一个，即散列函数为：h(k)=k%m。
 *   当应用除法散列法时，要避免选择m的某些值。例如，m不应为2的幂，因为如果m=2^p，则h(k)就是k的p个最低位数字。
 *   除非已知各种最低p位的排列形式为等可能的。一个不太接近2的整数幂的素数，常常是m的一个骄较好的选择
 *乘法散列法：
 *   构造散列函数的乘法散列法包含两个步骤：
 *   ①用关键字k乘以常数A(0<A<1)，并提取kA的小数部分。
 *   ②用m乘以这个数，再向下取整。
 *   即散列函数为：h(k)=m(kA mod 1)
 *   乘法散列法的一个优点是对m的选择不是特别关键，一般选择它为2的某个次幂。
 *   假设某计算机的字长为w位，而k正好可用一个单字表示。限制A为形如s/2^w的一个分数，其中s是一个取自0<s<2^w的整数
 *   ①先用w位整数s=A*2^w乘上k，其结果是一个2w位的值m2^w+n，这里m为乘积的高位字，n为乘积的低位字
 *   最佳的选择与待散列的数据的特征有关。
 *全域散列法：
 *   随机地选择散列函数，使之独立于要存储的关键字，这种方法称为全域散列法。
 *   全域散列法在执行开始时，就从一组精心设计的函数中，随机地选择一个作为散列函数。
 *   因为随机地选择散列函数，算法在每一次执行时都会有所不同，甚至对相同的输入都会如此。
 *定义：设F为一组有限散列函数，它将给定的关键字全域U映射到{0,1,...,m-1}中。这样的一个函数组称为全域的，
 *     如果对每一对不同的关键字k,l，满足f(k)=f(l)的函数f的个数至多为F/m。
 *     换句话说，如果从F中随机地选择一个散列函数，当关键字k≠l时，两者发生冲突的概率不大于1/m，
 *     这也是从集合{0,1,...,m-1}中独立地随机选择f(k)和f(l)时发生冲突的概率。
 *定理：如果f选自一组全域散列函数，将n个关键字散列到一个大小为m的表T中，并用链接法解决冲突，
 *     关键字k不在表中，则k被散列值其中的链表的期望长度至多为n/m。如果关键字k在表中，则包含关键字k的链表的期望长度至多为1+a.
 * Created by lihongyan on 2015/11/13.
 *
 */
public class Hash_Table {
    private class Node{
        private int key;
        private Node next;
        private Node front;
        public Node(){}
        public Node(int key){
            this.key = key;
            this.next = null;
            this.front = null;
        }
    }
    private Node[] T;
    private int size;
    public Hash_Table(){
        this.T = new Node[10];
        this.size = 0;
    }
    public void chained_hash_insert(){

    }
    public void chained_hash_delete(){

    }

    public void capacity(int n){
        if(this.T.length<n){

        }
    }
    public static void main(String[] args){

    }
}
